The present invention relates generally to bit-mapping, and more particularly, to methods of interleaving/de-interleaving with compressed mapping sequences.
In many types of communication channels, such as radio channels, the inherent noise causes bit errors to occur during transmission. In order to reduce bit errors, digital communication systems typically use error control codes to enable detection and/or correction of the bit errors at the receiver. These error control codes introduce controlled redundancy into the information transmitted over the communication channel, which can be used at the receiver to detect and/or correct errors in the received signal. Error detecting codes enable the receiver to detect bit errors. The receiver may then request retransmission of the information that was received in error. Error correcting codes enable the receiver to detect and correct bit errors without retransmission.
Convolutional codes are one type of forward error correcting code used in digital communication systems. Though very effective in correcting random bit errors that occur during transmission, convolutional codes are susceptible to burst errors. Random errors occur when individual bits in the transmitted bit sequence are corrupted by noise and received in error. Random errors are typically isolated and may be caused by noise in the communication channel. Burst errors occur when a series of adjacent or closely spaced bits are received in error and may be caused by fading in the communication channel. Many coding schemes have difficulty correcting burst errors.
Interleaving is a technique used to enhance the error correcting capabilities of error correcting codes, such as convolutional codes, to make them more effective against burst errors. Coded bits output by an encoder are reordered by an interleaver to spread the coded bits over time. This reordering of the coded bits in effect spreads long burst errors so that they appear to the decoder as independent random bit errors. An interleaver can be viewed as a one-to-one mapping function that maps input bits in an input sequence to a corresponding position in an equal-length output bit sequence.
Two techniques are commonly used to perform interleaving and de-interleaving—the lookup method and the calculation method. The lookup method uses pre-calculated mapping values for each input bit to map input bit positions in an input sequence to output bit positions in an output sequence. The pre-calculated mapping values comprise a mapping sequence that is stored in a look-up table. The interleaver/de-interleaver gets the output bit position for each input bit by a simple look-up operation. This look-up table method is relatively efficient in use of processing resources, but requires a relatively large amount of memory compared to the calculation approach. The calculation approach calculates the output bit position for each input bit in real time. The calculation method can be used when the mapping function can be expressed in closed form. The calculation method doesn't require any memory to store look-up tables at the cost of more processing resources.
The design of chip sets for digital communication systems is often constrained by memory rather than by processing resources. In such systems, the look-up table approach is inappropriate and a method that can achieve a better balance between memory and processing resources is often desired. Achieving a better balance between memory and processing resources may help in reducing the size and cost of chip sets for mobile communications.